#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

 struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
 };





//链表04：合并K个升序链表
class Solution1 {
public:
    struct compare
    {
        bool operator()(ListNode* a,ListNode* b)
        {
            return a->val > b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        priority_queue<ListNode*,vector<ListNode*>,compare> pq;

        for(auto it:lists)
        {
            if(it)
                pq.push(it);
        }
        ListNode* phead=new ListNode(0);
        ListNode* cur=phead;
        while(!pq.empty())
        {
            ListNode* min=pq.top();
            pq.pop();
            cur->next=min;
            cur=min;
            if(min->next)
                pq.push(min->next);
        }
        phead=phead->next;
        return phead;
    }
};


//链表05：K个一组翻转链表
class Solution2 {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        ListNode* cur=head;
        int size=0;
        while(cur)
        {
            cur=cur->next;
            size++;
        }
        if(k<=1)
            return head;
        if(size==2)
        {
            ListNode* tail=head->next;
            tail->next=head;
            head->next=nullptr;
            return tail;
        }
        //走到这里说明至少是一个三元素以上的链表
        ListNode*phead=new ListNode(0);
        phead->next=head;
        ListNode*prev=phead;
        ListNode*mid=prev->next;
        ListNode*tail=mid->next;
        while(size>k)//只有K刚好=size的时候需要单独处理，防止tail越界;
        {
            cur=mid;
            for(int i=0;i<k;i++)
            {               
                mid->next=prev;
                prev=mid;
                mid=tail;
                tail=tail->next; 
            }
            cur->next->next=prev;
            cur->next=mid;
            prev=cur;
            size-=k;
        }
        //走到这里分2种情
        //刚好剩最后一组，既size==k，需要单独考虑最后一次tail的越界界情况
        //剩最后一组长度<K的，不需要处理直接return
        if(size==k)
        {
            cur=mid;
            for(int i=0;i<k-1;i++)
            {               
                mid->next=prev;
                prev=mid;
                mid=tail;
                tail=tail->next; 
            }
            mid->next=prev;
            cur->next->next=mid;
            cur->next=nullptr;            
        }
        return phead->next;
    }
};

void test2()
{
    ListNode* head = new ListNode(1);
    ListNode* cur = head;
    for (int i = 2; i <= 5; i++)
    {
        ListNode* tmp = new ListNode(i);
        cur->next = tmp;
        cur = tmp;
    }
    Solution2 SL;
    SL.reverseKGroup(head, 5);
}

int main()
{
    test2();
    return 0;
}